
import numpy as np
import matplotlib.pyplot as plt

def f(x):
    return x*x-1

# 画示意图
x = np.arange(-4, 4, 0.1)
y = f(x)
plt.xlim(-4, 4); plt.ylim(-1, 12)
plt.xlabel("x",fontsize=15); plt.ylabel("y", fontsize=15)
xarrow = [2,1,-0.618, -3.235924]
plt.xticks(xarrow, xarrow )
for x1 in xarrow: # 画竖箭头
    plt.arrow( x1, -1, 0, f(x1)+1 )
for i in range(3): # 斜箭头
    plt.arrow(xarrow[i], f(xarrow[i]), xarrow[i+1]-xarrow[i], f(xarrow[i+1]) - f(xarrow[i]), width=0.05, color='red')
plt.plot(x, y)
plt.savefig("opt1d.png")

# 从初值a,b出发，得到嫌疑区间：b在a,c之间, f(b)小于f(a),f(c)
def opt1d1( a, b, f, max_iter ):
    if ( f(a) < f(b) ): # 确保：a -> b 为函数值下降方向
        c = a; a = b; b = c
    c = b + 1.618 * (b-a)
    iter = 0
    while( f(c) < f(b) and iter < max_iter ): # 寻找case: a<b<c, f(a)>f(b), f(c)>F(b)
        print("a=",a," b=",b," c=",c)
        a = b; b=c; c = b + 1.618 * (b-a); iter +=1
    if( iter == max_iter ):
        print("failed to get a zone for 1d-optimmization"); exit(1)
    else:
        return a,b,c

# 给定条件：b在a,c之间, f(b)小于f(a),f(c)
# 缩小嫌疑区间： [a,c] 或 [c,a]
def opt1d2( a, b, c, f, precision ):
    if not ( (a<b<c or a>b>c) and f(a)>f(b) and f(c)>f(b)):
        print("invalid input")
    while abs(c-a) > precision: # narrow down the suspicious zone
        d = a + 0.618 * (c-a)
        print( "a=", a, " b=", b, " c=", c, "d=", d )
        if b<d<c or b>d>c: # d is between b and c
            if f(d) < f(b):
                a = b; b = d
            else:
                c = d
        else: # d is between a and b
            if f(d) < f(b):
                c = b; b = d
            else:
                a = d
    return b

def opt1d(a,b,f,precision):
    a,b,c = opt1d1(a,b,f,10000)
    print("a=",a," b=",b," c=",c)
    return opt1d2(a,b,c,f,precision)

print("minimum of f(x) = x*x-1 is at x=", opt1d(1,2,f,1e-5))